package com.hao.tree;


import sun.font.TrueTypeFont;

/**
 * TODO
 *
 * @author 97472
 * @version 1.0F
 * @date 2021/6/7 15:49
 */
public class RDT <K extends Comparable<K>,V>{
    public static void main(String[] args) {

    }
    private final static boolean RED =true;
    private final static boolean BLACK =false;
    /**
     * 该二叉树的根节点
     */
    private Node root;
    /**
     * 二叉树的节点类，里面有key值，value值，left左节点，right右节点，size该节点下子树所有的节点（等于左右节点size和）
     */
    class Node{
        K k;
        V v;
        Node left;
        Node right;
        boolean color;
        int size;

        public Node(K k, V v,boolean color) {
            this.k = k;
            this.v = v;
            this.color = color;
        }

        @Override
        public String toString() {
            return "Node{" +
                    "k=" + k +
                    ", v=" + v +
                    ", left=" + left +
                    ", right=" + right +
                    ", size=" + size +
                    '}';
        }
    }

    /**
     * 判断一个节点是否是红色节点，默认空节点位黑色
     * @param node
     * @return
     */
    private boolean isRed(Node node){
        return node != null && node.color == RED;
    }
    public int height(){
        return height(root,0);
    }
    public int height(Node node, int height){
        if (node == null){
            return height;
        }
        height++;
        if (node.left == null){
            return height(node.right,height);
        }else if(node.right == null){
            return height(node.left,height);
        }else {
            int rightHeight = height(node.right,height);
            int leftHeight = height(node.left,height);
            return rightHeight > leftHeight ? rightHeight:leftHeight;
        }
    }
    /**
     * 获取二叉树的节点数
     * @return
     */
    public int size(){
        return size(root);
    }

    /**
     *  某个节点下的节点数
     * @param node
     * @return
     */
    private int size(Node node){
        return node == null ? 0 : node.size;
    }

    /**
     * 根据key值获取二叉树中相对应的value，如果找到则返回value，否则就返回null
     * @param key
     * @return
     */
    public V get(K key){
        Node node = get(root, key);
        return node==null?null:node.v;
    }

    /**
     *  根据和节点key值查找该节点下的key对应的value
     *  此方法是递归方法
     * @param node
     * @param key
     * @return
     */
    private Node get(Node node, K key){
        if (node == null){
            return null;
        }
        int compareTo = key.compareTo(node.k);
        if (compareTo > 0){
            return get(node.right,key);
        }else if(compareTo < 0){
            return get(node.left,key);
        }else {
            return node;
        }
    }

    /**
     *  左旋转 将右节点是红色节点的时候使用左旋转
     * @param node
     * @return
     */
    public Node rotateLeft (Node node){
        // 1.
        Node x = node.right;
        node.right = x.left;
        x.left = node;
        x.color = node.color;
        node.color = RED;
        x.size = node.size;
        node.size = size(node.left)+size(node.right)+1;
        return x;
    }
    /**
     *  右旋转 当连续两个左节点是红色节点的时候使用右旋转
     * @param node
     * @return
     */
    public Node rotateRight (Node node){
        Node x = node.left;
        node.left = x.right;
        x.right = node;
        x.color = node.color;
        node.color = RED;
        x.size = node.size;
        node.size = size(node.left)+size(node.right)+1;
        return x;
    }

    /**
     * 如果左右子节点都是红色节点，就将两个子节点变为黑色节点，将自己的颜色变为红色。
     * @param node
     * @return
     */
    public Node flipColors(Node node){
        node.left.color = BLACK;
        node.right.color = BLACK;
        node.color = RED;
        return node;
    }
    /**
     * 向二叉树中插入一对键值对，如果有该key就覆盖value值，如果没有就加入新的节点
     * @param key 键值对的key值
     * @param value 键值对的value值
     */
    public void put(K key,V value){
        root = put(root,key,value);
        root.color = BLACK;
    }

    /**
     * 向该节点下的子树中插入一键值对。
     * @param node 子树的根节点
     * @param key 键值对的key值
     * @param value 键值对的value值
     */
    private Node put(Node node, K key, V value){
        if (node == null){
            return new Node(key,value,RED);
        }
        int compareTo = key.compareTo(node.k);
        if (compareTo > 0){
            node.right = put(node.right,key,value);
        }else if(compareTo < 0){
            node.left = put(node.left,key,value);
        }else {
            node.v = value;
        }
        // 如果右节点是红色节点且左节点不是红色节点就进行左旋转
        if (isRed(node.right) && !isRed(node.left)){
            rotateLeft(node);
        }
        // 如果连续两个左节点都是红色的就进行右旋转
        if (isRed(node.left) && isRed(node.left.left)){
            rotateRight(node);
        }
        // 如果两个子节点都是红色节点，就进行节点颜色转换
        if (isRed(node.left) && isRed(node.right)){
            flipColors(node);
        }
        node.size = size(node.left) + size(node.right) + 1;
        return node;
    }
    public void deleteMin(){
        root = deleteMin(root);
    }
    public Node deleteMin(Node node){
        if (node.left == null){
            return node.right;
        }
        // 如果当前节点的左节点是2-节点但是兄弟节点兄弟节点不是2-节点。就将兄弟节点的一个键移到自己左节点上变成3-节点
        if (!isRed(node.left.left)&&isRed(node.right.left)){

        }
        if (!isRed(node.left.left)&&!isRed(node.right.left)){

        }
        node.left = deleteMin(node.left);
        node.size = size(node.left) + size(node.right) + 1;
        return node;
    }
    public void delete(K key){
        root = delete(root,key);
        // 找到要删除的节点
        // 找到替代要删除的节点的节点（）
    }
    public Node delete(Node node, K key){
        if (node == null){
            return null;
        }
        int compareTo = key.compareTo(node.k);
        if (compareTo > 0){
            node.right = delete(node.right,key);
        }else if(compareTo < 0){
            node.left = delete(node.left,key);
        }else {
            if (node.left == null){
                return node.right;
            }
            if (node.right == null){
                return node.left;
            }
            Node t = node;
            node = min(t.right);
            node.right = deleteMin(t.right);
            node.left = t.left;
        }
        node.size = size(node.left) + size(node.right) + 1;
        return node;
    }
    /**
     * 获取二叉树中最大值
     * @return
     */
    public V max (){
        Node max = max(root);
        return max.v;
    }

    private Node max (Node node){
        if (node.right == null){
            return node;
        }else {
            return max(node.right);
        }
    }

    /**
     * 获取二叉树中最小值
     * @return
     */
    public V min(){
        return min(root).v;
    }

    private Node min(Node node){
        if (node.left == null) {
            return node;
        } else {
            return min(node.left);
        }
    }

    @Override
    public String toString() {
        return "BST{" +
                "root=" + root +
                '}';
    }
}
